﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using MapColoring.MontadorMapa;

namespace MapColoring.CSP
{
    /// <summary>
    /// Contém métodos de resolução de problemas do tipo CSP,
    /// com 5 tipos de algoritmos possíveis de resolução
    /// </summary>
    public class CSP
    {
        #region Enum

        public enum Cores { Vermelho, Verde, Azul, Amarelo, SemCor };

        #endregion

        #region Campos Privados

        private int numCores;
        private List<Cores> cores = null;
        private List<Atribuicao> atribuicoes = null;
        private List<VariavelCSP> variaveisCSP = null;

        #endregion

        #region Propriedades

        /// <summary>
        /// Número de cores disponíveis para atribuição
        /// </summary>
        public int NumCores
        {
            get { return this.numCores; }
            set { this.numCores = value; }
        }

        /// <summary>
        /// Atribuições feitas a variáveis
        /// </summary>
        public List<Atribuicao> Atribuicoes
        {
            get { return this.atribuicoes; }
        }

        #endregion

        #region Construtores

        /// <summary>
        /// Contém métodos de resolução de problemas do tipo CSP,
        /// com 5 tipos de algoritmos possíveis de resolução
        /// </summary>
        /// <param name="numCores">número de cores disponíveis para atribuir às variáveis</param>
        /// <param name="mapa">mapa a ser colorido</param>
        public CSP(int numCores, Mapa mapa)
        {
            this.NumCores = numCores;
            this.atribuicoes = new List<Atribuicao>();
            initCores();
            initVariaveisCSP(mapa);
        }

        #endregion

        #region Inicializações

        /// <summary>
        /// Inicialização das cores utilizadas pelo algoritmo
        /// </summary>
        private void initCores()
        {
            cores = new List<Cores>();
            cores.Add(Cores.Vermelho);
            cores.Add(Cores.Verde);
            cores.Add(Cores.Azul);
            if (this.NumCores == 4)
            {
                cores.Add(Cores.Amarelo);
            }
        }

        /// <summary>
        /// Inicialização das variáveis do CSP
        /// </summary>
        /// <param name="mapa">mapa a ser colorido</param>
        private void initVariaveisCSP(Mapa mapa)
        {
            variaveisCSP = new List<VariavelCSP>();

            foreach (int variavel in mapa.Variaveis)
            {
                List<int> restricoes = new List<int>();
                for (int i = 0; i < mapa.Restricoes.Count; i++)
                {
                    if (mapa.Restricoes[i][0] == variavel)
                        restricoes.Add(mapa.Restricoes[i][1]);
                    if (mapa.Restricoes[i][1] == variavel)
                        restricoes.Add(mapa.Restricoes[i][0]);
                }

                variaveisCSP.Add(new VariavelCSP(variavel, restricoes, new List<CSP.Cores>(this.cores)));
            }
        }

        #endregion

        #region BacktrackingSearch

        /// <summary>
        /// Realiza uma busca em profundidade com backtracking para colorir o mapa
        /// </summary>
        /// <param name="mapa">O mapa a colorir</param>
        /// <returns>'true' se uma solução foi encontrado e 'false' se ocorreu uma falha</returns>
        public bool backtrackingSearch()
        {
            return recursiveBacktracking();
        }

        /// <summary>
        /// Método recursivo iterativo utilizando algoritmo de Backtracking simples
        /// </summary>
        /// <returns>true, se achar solução</returns>
        private bool recursiveBacktracking()
        {
            if (verificaAtribuicoesCompletas())
                return true;

            VariavelCSP variavel = selecionaVariavelSemAtribuicao();
            foreach (Cores cor in this.cores)
            {
                Program.nIteracoes += 1;
                if (verificaRestricoes(cor, variavel))
                {
                    atribuicoes.Add(new Atribuicao(variavel.IdVariavel, cor));
                    bool result = recursiveBacktracking();
                    if (result)
                        return result;
                    atribuicoes = removeAtribuicao(variavel.IdVariavel);
                }
            }
            return false;
        }

        /// <summary>
        /// Retorna próxima variável sem atribuição de valor
        /// </summary>
        /// <returns>Variável ´sem valor associado</returns>
        private VariavelCSP selecionaVariavelSemAtribuicao()
        {
            foreach (VariavelCSP v in this.variaveisCSP)
            {
                bool flag = true;
                foreach (Atribuicao a in this.atribuicoes)
                {
                    if (v.IdVariavel == a.IdVariavel)
                        flag = false;
                }

                if (flag)
                    return v;
            }

            return null;
        }

        #endregion

        #region BacktrackingSearch com MRV

        /// <summary>
        /// Realiza uma busca em profundidade com backtracking para colorir o mapa usando a heuristica MRV
        /// </summary>
        /// <param name="mapa">O mapa a colorir</param>
        /// <returns>'true' se uma solução foi encontrado e 'false' se ocorreu uma falha</returns>
        public bool backtrackingSearchMRV()
        {
            return recursiveBacktrackingMRV();
        }

        /// <summary>
        /// Método recursivo iterativo do algoritmo com Backtracking e heurística MRV
        /// </summary>
        /// <returns>true, se encontrar solução</returns>
        private bool recursiveBacktrackingMRV()
        {
            if (verificaAtribuicoesCompletas())
                return true;

            VariavelCSP variavel = selecionaVariavelSemAtribuicaoMRV();
            foreach (Cores cor in this.cores)
            {
                Program.nIteracoes += 1;
                if (verificaRestricoes(cor, variavel))
                {
                    atribuicoes.Add(new Atribuicao(variavel.IdVariavel, cor));
                    atualizaDominios(variavel, cor);
                    bool result = recursiveBacktrackingMRV();
                    if (result)
                        return result;
                    atribuicoes = removeAtribuicao(variavel.IdVariavel);
                }
            }
            return false;
        }

        /// <summary>
        /// Faz seleção da próxima variável utilizando heurística MRV
        /// </summary>
        /// <returns>variável que terá valor atribuído</returns>
        private VariavelCSP selecionaVariavelSemAtribuicaoMRV()
        {
            int count = this.numCores + 1;
            VariavelCSP variavel = null;
            foreach (VariavelCSP v in this.variaveisCSP)
            {
                //Verifica se variável já foi atribuida
                bool foiAtribuida = false;

                for (int i = 0; i < this.atribuicoes.Count; i++)
                {
                    if (v.IdVariavel == this.atribuicoes[i].IdVariavel)
                    {
                        foiAtribuida = true;
                        break;
                    }
                }

                if (foiAtribuida)
                    continue;

                //se não foi atribuída, verifica o tamanho do domínio dela
                if (v.Dominio.Count < count)
                {
                    count = v.Dominio.Count;
                    variavel = v;
                }
            }

            return variavel;
        }

        /// <summary>
        /// Atualiza domínio de todas as variáveis, devido a uma nova atribuição
        /// </summary>
        /// <param name="variavel">nova variável que foi atribuída</param>
        /// <param name="cor">valor atribuído à nova variável</param>
        private void atualizaDominios(VariavelCSP variavel, Cores cor)
        {
            foreach (int vizinho in variavel.Restricoes)
            {
                VariavelCSP v = obtemVariavelCSP(vizinho);
                v.RemovePossibilidade(cor);
            }
        }
        
        #endregion

        #region Foward Checking

        /// <summary>
        /// Realiza uma busca em profundidade com backtracking usando foward checking
        /// </summary>
        /// <param name="mapa">O mapa a colorir</param>
        /// <returns>'true' se uma solução foi encontrado e 'false' se ocorreu uma falha</returns>
        public bool fowardChecking()
        {
            return recursiveBacktrackingFowardCheking();
        }

        /// <summary>
        /// Método recursivo do algoritmo de forward checking
        /// </summary>
        /// <returns>true, se for encontrada uma solução</returns>
        private bool recursiveBacktrackingFowardCheking()
        {
            if (verificaAtribuicoesCompletas())
                return true;

            if (!verificaExistenciaPossibilidade())
                return false;

            VariavelCSP variavel = selecionaVariavelSemAtribuicao();
            foreach (Cores cor in this.cores)
            {
                if (verificaRestricoesForwardChecking(cor, variavel))
                {
                    Program.nIteracoes += 1;

                    atribuicoes.Add(new Atribuicao(variavel.IdVariavel, cor));
                    atualizaDominios(variavel, cor);
                    bool result = recursiveBacktrackingFowardCheking();
                    if (result)
                        return result;
                    atribuicoes = removeAtribuicao(variavel.IdVariavel);
                }
            }
            return false;
        }

        /// <summary>
        /// Verifica se alguma das variáveis possui domínio nulo
        /// </summary>
        /// <returns>true, se todas as variáveis que ainda não foram atribuídas possuírem pelo
        /// menos um valor em seu domínio</returns>
        private bool verificaExistenciaPossibilidade()
        {
            foreach (VariavelCSP v in this.variaveisCSP)
            {
                if ((this.obtemCorAtribuida(v.IdVariavel) == Cores.SemCor) && v.Dominio.Count == 0)
                    return false;
            }

            return true;
        }

        #endregion

        #region Foward Checking com MRV

        /// <summary>
        /// Realiza uma busca em profundidade com backtracking usando foward checking com a heuristica MRV
        /// </summary>
        /// <param name="mapa">O mapa a colorir</param>
        /// <returns>'true' se uma solução foi encontrado e 'false' se ocorreu uma falha</returns>
        public bool fowardCheckingMRV()
        {
            return recursiveBacktrackingFowardChekingMRV();
        }

        /// <summary>
        /// Método recursivo de iteração do algoritmo Forward Checking com MRV
        /// </summary>
        /// <returns>true, se o algoritmo achar uma solução</returns>
        private bool recursiveBacktrackingFowardChekingMRV()
        {
            if (verificaAtribuicoesCompletas())
                return true;

            if (!verificaExistenciaPossibilidade())
                return false;

            VariavelCSP variavel = selecionaVariavelSemAtribuicaoMRV();
            foreach (Cores cor in this.cores)
            {
                if (verificaRestricoesForwardChecking(cor, variavel))
                {
                    Program.nIteracoes += 1;

                    atribuicoes.Add(new Atribuicao(variavel.IdVariavel, cor));
                    atualizaDominios(variavel, cor);
                    bool result = recursiveBacktrackingFowardChekingMRV();
                    if (result)
                        return result;
                    atribuicoes = removeAtribuicao(variavel.IdVariavel);
                }
            }
            return false;
        }
        
        #endregion

        #region Min Conflicts

        /// <summary>
        /// Faz atribuições aleatórias às variáveis
        /// </summary>
        private void geraSolucaoAleatoria()
        {
            Random rdn = new Random();
            foreach (VariavelCSP v in this.variaveisCSP)
            {
                int cor = rdn.Next(this.numCores);
                this.atribuicoes.Add(new Atribuicao(v.IdVariavel, (Cores)Enum.Parse(typeof(Cores),cor + "")));
            }
        }

        /// <summary>
        /// Algoritmo de busca local com minimização de conflitos
        /// </summary>
        /// <param name="numMaxPassos">número máximo de passos até se perceber que não é possível atingir uma solução</param>
        /// <returns>true, se achou solução</returns>
        public bool minConflicts(int numMaxPassos)
        {
            this.geraSolucaoAleatoria();
            for (int i = 0; i < numMaxPassos; i++)
            {
                if (this.EhSolucao())
                    return true;
                
                Program.nIteracoes += 1;

                List<Object> mudanca = this.obtemMudancaMenosConflitos();
                int variavelMudanca = (int)mudanca[0];
                Cores corMudanca = (Cores)mudanca[1];

                mudaCorAtribuicao(variavelMudanca, corMudanca);
            }

            return false;
        }

        /// <summary>
        /// Verifica se estado atual do CSP corresponde a uma solução do problema
        /// </summary>
        /// <returns>true, se o estado atual configurar uma solução ao problema</returns>
        private bool EhSolucao()
        {
            foreach (Atribuicao a in this.atribuicoes)
            {
                Cores cor = a.Cor;
                VariavelCSP variavel = obtemVariavelCSP(a.IdVariavel);
                foreach (int v in variavel.Restricoes)
                {
                    if (cor == obtemCorAtribuida(v))
                    {
                        return false;
                    }
                }
            }

            return true;
        }
        
        /// <summary>
        /// Percorre todas as possibilidades de mudança de variáveis a partir do estado atual 
        /// e vê qual delas possui menos conflitos
        /// </summary>
        /// <returns>
        /// Mudança a ser executada: 
        /// Trata-se de uma lista com
        ///     [0] variável
        ///     [1] cor
        /// </returns>
        private List<Object> obtemMudancaMenosConflitos()
        {
            List<Object> mudanca = new List<object>();
            
            int conflitosMin = int.MaxValue;
            Cores corMudanca = Cores.SemCor;
            int variavelMudanca = -1;

            // para cada uma das variáveis do CSP
            for (int i = 0; i < this.variaveisCSP.Count; i++)
            {
                int conflitosBase = this.calculaConflitosBase(this.variaveisCSP[i]);
                int conflitosVerm = conflitosBase;
                int conflitosVerde = conflitosBase;
                int conflitosAzul = conflitosBase;
                int conflitosAmarelo = conflitosBase;

                VariavelCSP vCSP = this.variaveisCSP[i];
                Cores corVCSP = this.obtemCorAtribuida(vCSP.IdVariavel);
                
                //calcula o número de conflitos para a mudança de vCSP para cada cor
                foreach (int v in vCSP.Restricoes)
                {
                    Cores cor = obtemCorAtribuida(v);
                    switch (cor)
                    {
                        case Cores.Vermelho:
                            conflitosVerm++;
                            break;
                        case Cores.Verde:
                            conflitosVerde++;
                            break;
                        case Cores.Azul:
                            conflitosAzul++;
                            break;
                        case Cores.Amarelo:
                            conflitosAmarelo++;
                            break;
                    }
                }

                // marca como mudança com conflitos mínimos se o número de conflitos for menor
                // além disso, não deixa a variável "mudar" para a mesma cor
                if (conflitosVerm < conflitosMin && corVCSP != Cores.Vermelho)
                {
                    conflitosMin = conflitosVerm;
                    corMudanca = Cores.Vermelho;
                    variavelMudanca = vCSP.IdVariavel;
                }
                if (conflitosVerde < conflitosMin && corVCSP != Cores.Verde)
                {
                    conflitosMin = conflitosVerde;
                    corMudanca = Cores.Verde;
                    variavelMudanca = vCSP.IdVariavel;
                }
                if (conflitosAzul < conflitosMin && corVCSP != Cores.Azul)
                {
                    conflitosMin = conflitosAzul;
                    corMudanca = Cores.Azul;
                    variavelMudanca = vCSP.IdVariavel;
                }
                if (conflitosAmarelo < conflitosMin && corVCSP != Cores.Amarelo && this.numCores >= 4)
                {
                    conflitosMin = conflitosAmarelo;
                    corMudanca = Cores.Amarelo;
                    variavelMudanca = vCSP.IdVariavel;
                }
            }

            mudanca.Add(variavelMudanca);
            mudanca.Add(corMudanca);
            return mudanca;
        }

        /// <summary>
        /// Muda atribuição de cor de uma variável
        /// </summary>
        /// <param name="variavel">variável que terá atribuição modificada</param>
        /// <param name="cor">nova cor a ser atribuída</param>
        private void mudaCorAtribuicao(int variavel, Cores cor)
        {
            foreach (Atribuicao a in this.atribuicoes)
            {
                if (variavel == a.IdVariavel)
                    a.Cor = cor;
            }
        }

        /// <summary>
        /// Calcula o número de conflitos obtidos sem levar em conta a variável passada como parâmetro
        /// </summary>
        /// <param name="variavel">Variável que não será levada em conta para a contagem de conflitos</param>
        /// <returns>número de conflitos ignorando valor da variável passada</returns>
        private int calculaConflitosBase(VariavelCSP variavelIgn)
        {
            int conflitos = 0;

            //para cada uma das variáveis do CSP
            for (int i = 0; i < this.variaveisCSP.Count; i++)
            {
                VariavelCSP variavel = this.variaveisCSP[i];
                if (variavel.IdVariavel == variavelIgn.IdVariavel)
                    continue;

                for (int j = 0; j < variavel.Restricoes.Count; j++)
                {
                    VariavelCSP variavel2 = this.obtemVariavelCSP(variavel.Restricoes[j]);
                    if (variavel.Restricoes[j] == variavelIgn.IdVariavel)
                        continue;

                    if (this.obtemCorAtribuida(variavel.Restricoes[j]) == this.obtemCorAtribuida(variavel.IdVariavel))
                        conflitos++;
                }
            }

            //conta o dobro de vezes
            return (conflitos / 2);
        }

        #endregion

        #region Métodos Privados

        /// <summary>
        /// Verifica se todas as variáveis possuem uma atribuição
        /// </summary>
        /// <returns>true, se todas as variáveis tiveram valores atribuídos</returns>
        private bool verificaAtribuicoesCompletas()
        {
            int count = 0;
            foreach (VariavelCSP v in this.variaveisCSP)
            {
                foreach (Atribuicao a in this.atribuicoes)
                {
                    if (a.IdVariavel == v.IdVariavel)
                        count++;
                }
            }

            if (count == this.variaveisCSP.Count)
                return true;
            return false;
        }

        /// <summary>
        /// Verifica se a cor pode ser atribuída à variável, respeitando as restrições
        /// </summary>
        /// <param name="cor">cor da variável</param>
        /// <param name="variavel">variável a ser testada</param>
        /// <returns>true, se é possível atribuir cor à variável, repseitando as restrições</returns>
        private bool verificaRestricoes(Cores cor, VariavelCSP variavel)
        {
            foreach (int v in variavel.Restricoes)
            {
                if (contemVariavel(v))
                {
                    Cores c = obtemCorAtribuida(v);
                    if (c == cor)
                        return false;
                }
            }

            return true;
        }

        /// <summary>
        /// Verifica se a cor pode ser atribuída à variável, respeitando as restrições. Este método é
        /// utilizado pelo agloritmmo Forward Checking e possui um tempo de execução menor do que o método
        /// 'verificaRestrições'
        /// </summary>
        /// <param name="cor">cor da variável</param>
        /// <param name="variavel">variável a ser testada</param>
        /// <returns>true, se é possível atribuir cor à variável, repseitando as restrições</returns>
        private bool verificaRestricoesForwardChecking(Cores cor, VariavelCSP variavel)
        {
            return variavel.Dominio.Contains(cor);
        }

        /// <summary>
        /// Retorna cor atribuída à variável
        /// </summary>
        /// <param name="variavel">variável</param>
        /// <returns>cor atribuída à variável</returns>
        private Cores obtemCorAtribuida(int variavel)
        {
            foreach (Atribuicao a in this.atribuicoes)
            {
                if (a.IdVariavel == variavel)
                    return a.Cor;
            }

            return Cores.SemCor;
        }

        /// <summary>
        /// Verifica se variável já teve valor atribuído
        /// </summary>
        /// <param name="variavel">Variáavel a ser verificada</param>
        /// <returns>true, se teve valor atribuído</returns>
        private bool contemVariavel(int variavel)
        {
            foreach (Atribuicao a in this.atribuicoes)
            {
                if (a.IdVariavel == variavel)
                    return true;
            }

            return false;
        }

        /// <summary>
        /// Remove atribuição de valor feita à variável
        /// </summary>
        /// <param name="variavel">variável que terá atribuição removida</param>
        /// <returns>lista de atribuições após remoção</returns>
        private List<Atribuicao> removeAtribuicao(int variavel)
        {
            int count = 0;
            int index = 0;
            foreach (Atribuicao a in this.atribuicoes)
            {
                if (a.IdVariavel == variavel)
                    index = count;
                count++;
            }
            atribuicoes.RemoveAt(index);

            return atribuicoes;
        }

        /// <summary>
        /// Obtem objeto VariávelCSP a partir do id da variável fornecido
        /// </summary>
        /// <param name="variavel">id da variável a ser obtida</param>
        /// <returns>VariávelCSP correspondente ao id fornecido</returns>
        private VariavelCSP obtemVariavelCSP(int variavel)
        {
            foreach (VariavelCSP v in this.variaveisCSP)
                if (v.IdVariavel == variavel)
                    return v;

            return null;
        }
        
        #endregion
    }
}
